/*
 * Copyright (c) 2022 Huawei Device Co., Ltd.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

class Crypto {
    public static final int CRYPTO_NUMBER_0XFFFFFF = 0xffffff;
    public static final int CRYPTO_NUMBER_0XEFCAFE = 0xefcafe;
    public static final int CRYPTO_NUMBER_0 = 0;
    public static final int CRYPTO_NUMBER_1 = 1;
    public static final int CRYPTO_NUMBER_2 = 2;
    public static final int CRYPTO_NUMBER_3 = 3;
    public static final int CRYPTO_NUMBER_5 = 5;
    public static final int CRYPTO_NUMBER_7 = 7;
    public static final int CRYPTO_NUMBER_11 = 11;
    public static final int CRYPTO_NUMBER_13 = 13;
    public static final int CRYPTO_NUMBER_17 = 17;
    public static final int CRYPTO_NUMBER_19 = 19;
    public static final int CRYPTO_NUMBER_23 = 23;
    public static final int CRYPTO_NUMBER_29 = 29;
    public static final int CRYPTO_NUMBER_31 = 31;
    public static final int CRYPTO_NUMBER_37 = 37;
    public static final int CRYPTO_NUMBER_41 = 41;
    public static final int CRYPTO_NUMBER_43 = 43;
    public static final int CRYPTO_NUMBER_47 = 47;
    public static final int CRYPTO_NUMBER_53 = 53;
    public static final int CRYPTO_NUMBER_59 = 59;
    public static final int CRYPTO_NUMBER_61 = 61;
    public static final int CRYPTO_NUMBER_67 = 67;
    public static final int CRYPTO_NUMBER_71 = 71;
    public static final int CRYPTO_NUMBER_73 = 73;
    public static final int CRYPTO_NUMBER_79 = 79;
    public static final int CRYPTO_NUMBER_83 = 83;
    public static final int CRYPTO_NUMBER_89 = 89;
    public static final int CRYPTO_NUMBER_97 = 97;
    public static final int CRYPTO_NUMBER_101 = 101;
    public static final int CRYPTO_NUMBER_103 = 103;
    public static final int CRYPTO_NUMBER_107 = 107;
    public static final int CRYPTO_NUMBER_109 = 109;
    public static final int CRYPTO_NUMBER_113 = 113;
    public static final int CRYPTO_NUMBER_127 = 127;
    public static final int CRYPTO_NUMBER_131 = 131;
    public static final int CRYPTO_NUMBER_137 = 137;
    public static final int CRYPTO_NUMBER_139 = 139;
    public static final int CRYPTO_NUMBER_149 = 149;
    public static final int CRYPTO_NUMBER_151 = 151;
    public static final int CRYPTO_NUMBER_157 = 157;
    public static final int CRYPTO_NUMBER_163 = 163;
    public static final int CRYPTO_NUMBER_167 = 167;
    public static final int CRYPTO_NUMBER_173 = 173;
    public static final int CRYPTO_NUMBER_179 = 179;
    public static final int CRYPTO_NUMBER_181 = 181;
    public static final int CRYPTO_NUMBER_191 = 191;
    public static final int CRYPTO_NUMBER_193 = 193;
    public static final int CRYPTO_NUMBER_197 = 197;
    public static final int CRYPTO_NUMBER_199 = 199;
    public static final int CRYPTO_NUMBER_211 = 211;
    public static final int CRYPTO_NUMBER_223 = 223;
    public static final int CRYPTO_NUMBER_227 = 227;
    public static final int CRYPTO_NUMBER_229 = 229;
    public static final int CRYPTO_NUMBER_233 = 233;
    public static final int CRYPTO_NUMBER_239 = 239;
    public static final int CRYPTO_NUMBER_241 = 241;
    public static final int CRYPTO_NUMBER_251 = 251;
    public static final int CRYPTO_NUMBER_257 = 257;
    public static final int CRYPTO_NUMBER_263 = 263;
    public static final int CRYPTO_NUMBER_269 = 269;
    public static final int CRYPTO_NUMBER_271 = 271;
    public static final int CRYPTO_NUMBER_277 = 277;
    public static final int CRYPTO_NUMBER_281 = 281;
    public static final int CRYPTO_NUMBER_283 = 283;
    public static final int CRYPTO_NUMBER_293 = 293;
    public static final int CRYPTO_NUMBER_307 = 307;
    public static final int CRYPTO_NUMBER_311 = 311;
    public static final int CRYPTO_NUMBER_313 = 313;
    public static final int CRYPTO_NUMBER_317 = 317;
    public static final int CRYPTO_NUMBER_331 = 331;
    public static final int CRYPTO_NUMBER_337 = 337;
    public static final int CRYPTO_NUMBER_347 = 347;
    public static final int CRYPTO_NUMBER_349 = 349;
    public static final int CRYPTO_NUMBER_353 = 353;
    public static final int CRYPTO_NUMBER_359 = 359;
    public static final int CRYPTO_NUMBER_367 = 367;
    public static final int CRYPTO_NUMBER_373 = 373;
    public static final int CRYPTO_NUMBER_379 = 379;
    public static final int CRYPTO_NUMBER_383 = 383;
    public static final int CRYPTO_NUMBER_389 = 389;
    public static final int CRYPTO_NUMBER_397 = 397;
    public static final int CRYPTO_NUMBER_401 = 401;
    public static final int CRYPTO_NUMBER_409 = 409;
    public static final int CRYPTO_NUMBER_419 = 419;
    public static final int CRYPTO_NUMBER_421 = 421;
    public static final int CRYPTO_NUMBER_431 = 431;
    public static final int CRYPTO_NUMBER_433 = 433;
    public static final int CRYPTO_NUMBER_439 = 439;
    public static final int CRYPTO_NUMBER_443 = 443;
    public static final int CRYPTO_NUMBER_449 = 449;
    public static final int CRYPTO_NUMBER_457 = 457;
    public static final int CRYPTO_NUMBER_461 = 461;
    public static final int CRYPTO_NUMBER_463 = 463;
    public static final int CRYPTO_NUMBER_467 = 467;
    public static final int CRYPTO_NUMBER_479 = 479;
    public static final int CRYPTO_NUMBER_487 = 487;
    public static final int CRYPTO_NUMBER_491 = 491;
    public static final int CRYPTO_NUMBER_499 = 499;
    public static final int CRYPTO_NUMBER_503 = 503;
    public static final int CRYPTO_NUMBER_509 = 509;
    public static final int CRYPTO_NUMBER_26 = 26;
    public static final int CRYPTO_NUMBER_0X4000000 = 0x4000000;
    public static final int CRYPTO_NUMBER_0X3FFFFFF = 0x3ffffff;
    public static final int CRYPTO_NUMBER_0X7FFF = 0x7fff;
    public static final int CRYPTO_NUMBER_15 = 15;
    public static final int CRYPTO_NUMBER_0X3FFFFFFF = 0x3fffffff;
    public static final int CRYPTO_NUMBER_30 = 30;
    public static final int CRYPTO_NUMBER_0X3FFF = 0x3fff;
    public static final int CRYPTO_NUMBER_14 = 14;
    public static final int CRYPTO_NUMBER_28 = 28;
    public static final int CRYPTO_NUMBER_0XFFFFFFF = 0xfffffff;
    public static final int CRYPTO_NUMBER_0X1FFF = 0x1fff;
    public static final int CRYPTO_NUMBER_52 = 52;
    public static final int CRYPTO_NUMBER_9 = 9;
    public static final int CRYPTO_NUMBER_36 = 36;
    public static final int CRYPTO_NUMBER_256 = 256;
    public static final int CRYPTO_NUMBER_16 = 16;
    public static final int CRYPTO_NUMBER_4 = 4;
    public static final int CRYPTO_NUMBER_8 = 8;
    public static final int CRYPTO_NUMBER_32 = 32;
    public static final int CRYPTO_NUMBER_0XFF = 0xff;
    public static final int CRYPTO_NUMBER_0X80 = 0x80;
    public static final int CRYPTO_NUMBER_0XF = 0xf;
    public static final int CRYPTO_NUMBER_0XFFFF = 0xffff;
    public static final long CRYPTO_NUMBER_0XFFFFFFFF = 0xffffffffL;
    public static final int CRYPTO_NUMBER_24 = 24;
    public static final int CRYPTO_NUMBER_10 = 10;
    public static final int CRYPTO_NUMBER_18 = 18;
    public static final int CRYPTO_NUMBER_48 = 48;
    public static final int CRYPTO_NUMBER_144 = 144;
    public static final int CRYPTO_NUMBER_768 = 768;
    public static final int CRYPTO_NUMBER_6 = 6;
    public static final int CRYPTO_NUMBER_255 = 255;
    public static final long CRYPTO_NUMBER_1122926989487 = 1122926989487L;
    public static final int CRYPTO_NUMBER_65536 = 65536;
    public static final int CRYPTO_NUMBER_0X10 = 0x10;
    public static final int CRYPTO_NUMBER_1000 = 1000;
    public static final int CRYPTO_RUNCOUNT_120 = 120;

    // Bits per digit
    public static int dbits;
    public static int bIDB;
    public static int bIDM;
    public static int bIDV;
	
    public static int bIFP;
    public static long bIFV;
    public static int bIF1;
    public static int bIF2;

    public static int dv = 0;

    // JavaScript engine analysis
    public long canary = 0xdeadbeefcafeL;
    public boolean jLm = (canary & CRYPTO_NUMBER_0XFFFFFF) == CRYPTO_NUMBER_0XEFCAFE;

    public static int[] lowprimes = new int[]{
	CRYPTO_NUMBER_2, CRYPTO_NUMBER_3, CRYPTO_NUMBER_5, CRYPTO_NUMBER_7, CRYPTO_NUMBER_11, CRYPTO_NUMBER_13, CRYPTO_NUMBER_17, CRYPTO_NUMBER_19, 
	CRYPTO_NUMBER_23, CRYPTO_NUMBER_29, CRYPTO_NUMBER_31, CRYPTO_NUMBER_37, CRYPTO_NUMBER_41, CRYPTO_NUMBER_43, CRYPTO_NUMBER_47, CRYPTO_NUMBER_53, 
	CRYPTO_NUMBER_59, CRYPTO_NUMBER_61, CRYPTO_NUMBER_67, CRYPTO_NUMBER_71, CRYPTO_NUMBER_73, CRYPTO_NUMBER_79, CRYPTO_NUMBER_83, CRYPTO_NUMBER_89, 
	CRYPTO_NUMBER_97, CRYPTO_NUMBER_101, CRYPTO_NUMBER_103, CRYPTO_NUMBER_107, CRYPTO_NUMBER_109, CRYPTO_NUMBER_113, CRYPTO_NUMBER_127, CRYPTO_NUMBER_131, 
	CRYPTO_NUMBER_137, CRYPTO_NUMBER_139, CRYPTO_NUMBER_149, CRYPTO_NUMBER_151, CRYPTO_NUMBER_157, CRYPTO_NUMBER_163, CRYPTO_NUMBER_167, CRYPTO_NUMBER_173, 
	CRYPTO_NUMBER_179, CRYPTO_NUMBER_181, CRYPTO_NUMBER_191, CRYPTO_NUMBER_193, CRYPTO_NUMBER_197, CRYPTO_NUMBER_199, CRYPTO_NUMBER_211, CRYPTO_NUMBER_223, 
	CRYPTO_NUMBER_227, CRYPTO_NUMBER_229, CRYPTO_NUMBER_233, CRYPTO_NUMBER_239, CRYPTO_NUMBER_241, CRYPTO_NUMBER_251, CRYPTO_NUMBER_257, CRYPTO_NUMBER_263, 
	CRYPTO_NUMBER_269, CRYPTO_NUMBER_271, CRYPTO_NUMBER_277, CRYPTO_NUMBER_281, CRYPTO_NUMBER_283, CRYPTO_NUMBER_293, CRYPTO_NUMBER_307, CRYPTO_NUMBER_311, 
	CRYPTO_NUMBER_313, CRYPTO_NUMBER_317, CRYPTO_NUMBER_331, CRYPTO_NUMBER_337, CRYPTO_NUMBER_347, CRYPTO_NUMBER_349, CRYPTO_NUMBER_353, CRYPTO_NUMBER_359, 
	CRYPTO_NUMBER_367, CRYPTO_NUMBER_373, CRYPTO_NUMBER_379, CRYPTO_NUMBER_383, CRYPTO_NUMBER_389, CRYPTO_NUMBER_397, CRYPTO_NUMBER_401, CRYPTO_NUMBER_409, 
	CRYPTO_NUMBER_419, CRYPTO_NUMBER_421, CRYPTO_NUMBER_431, CRYPTO_NUMBER_433, CRYPTO_NUMBER_439, CRYPTO_NUMBER_443, CRYPTO_NUMBER_449, CRYPTO_NUMBER_457, 
	CRYPTO_NUMBER_461, CRYPTO_NUMBER_463, CRYPTO_NUMBER_467, CRYPTO_NUMBER_479, CRYPTO_NUMBER_487, CRYPTO_NUMBER_491, CRYPTO_NUMBER_499, CRYPTO_NUMBER_503, 
	CRYPTO_NUMBER_509};
    public static int lplim = (1 << CRYPTO_NUMBER_26) / lowprimes[lowprimes.length - 1];

    // am: Compute w_j += (x*this_i), propagate carries,
    // c is initial carry, returns final carry.
    // c < 3*dvalue, x < 2*dvalue, this_i < dvalue
    // We need to select the fastest one that works in this environment.

    // am1: use a single mult and divide to get the high bits,
    // max digit bits should be 26 because
    // max internal value = 2*dvalue^2-2*dvalue (< 2^53)
    public AmBlock am1 = (ArrayList<Integer> array, int i, int x, BigInteger w, int j, int c, int n) -> {
        int tempI = i;
        int tempJ = j;
        int tempC = c;
        int tempN = n - 1;
        while (tempN >= 0) {
            int v = x * array.get(tempI) + w.array.get(tempJ) + tempC;
            tempC = (int) Math.floor((double) v / CRYPTO_NUMBER_0X4000000);
            w.array = Benchmark.insertValue(w.array, v & CRYPTO_NUMBER_0X3FFFFFF, tempJ);
            tempI += 1;
            tempJ += 1;
            tempN -= 1;
        }
        return tempC;
    };

    // am2 avoids a big mult-and-extract completely.
    // Max digit bits should be <= 30 because we do bitwise ops
    // on values up to 2*hdvalue^2-hdvalue-1 (< 2^31)
    public AmBlock am2 = (ArrayList<Integer> array, int i, int x, BigInteger w, int j, int c, int n) -> {
        int xl = x & CRYPTO_NUMBER_0X7FFF;
        int xh = x >> CRYPTO_NUMBER_15;
        int tempI = i;
        int tempJ = j;
        int tempC = c;
        int tempN = n - 1;
        while (tempN >= 0) {
            int l = array.get(tempI) & CRYPTO_NUMBER_0X7FFF;
            int h = array.get(tempI) >> CRYPTO_NUMBER_15;
            int m = xh * l + h * xl;
            l = xl * l + ((m & CRYPTO_NUMBER_0X7FFF) << CRYPTO_NUMBER_15) + w.array.get(tempJ) + (tempC & CRYPTO_NUMBER_0X3FFFFFFF);
            tempC = (l >>> CRYPTO_NUMBER_30) + (m >>> CRYPTO_NUMBER_15) + xh * h + (tempC >>> CRYPTO_NUMBER_30);
            w.array = Benchmark.insertValue(w.array, l & CRYPTO_NUMBER_0X3FFFFFFF, tempJ);
            tempI += 1;
            tempJ += 1;
            tempN -= 1;
        }
        return tempC;
    };

    // Alternately, set max digit bits to 28 since some
    // browsers slow down when dealing with 32-bit numbers.
    public static AmBlock am3 = (ArrayList<Integer> array, int i, int x, BigInteger w, int j, int c, int n) -> {
        int xl = x & CRYPTO_NUMBER_0X3FFF;
        int xh = x >> CRYPTO_NUMBER_14;
        int tempI = i;
        int tempJ = j;
        int tempC = c;
        int tempN = n - 1;
        while (tempN >= 0) {
            int l = array.get(tempI) & CRYPTO_NUMBER_0X3FFF;
            int h = array.get(tempI) >> CRYPTO_NUMBER_14;
            int m = xh * l + h * xl;
            l = xl * l + ((m & CRYPTO_NUMBER_0X3FFF) << CRYPTO_NUMBER_14) + w.array.get(tempJ) + tempC;
            tempC = (l >> CRYPTO_NUMBER_28) + (m >> CRYPTO_NUMBER_14) + xh * h;
            w.array = Benchmark.insertValue(w.array, l & CRYPTO_NUMBER_0XFFFFFFF, tempJ);
            tempI += 1;
            tempJ += 1;
            tempN -= 1;
        }
        return tempC;
    };

    // This is tailored to VMs with 2-bit tagging. It makes sure
    // that all the computations stay within the 29 bits available.
    public AmBlock am4 = (ArrayList<Integer> array, int i, int x, BigInteger w, int j, int c, int n) -> {
        int xl = x & CRYPTO_NUMBER_0X1FFF;
        int xh = x >> CRYPTO_NUMBER_13;
        int tempI = i;
        int tempJ = j;
        int tempC = c;
        int tempN = n - 1;
        while (tempN >= 0) {
            int l = array.get(tempI) & CRYPTO_NUMBER_0X1FFF;
            int h = array.get(tempI) >> CRYPTO_NUMBER_13;
            int m = xh * l + h * xl;
            l = xl * l + ((m & CRYPTO_NUMBER_0X1FFF) << CRYPTO_NUMBER_13) + w.array.get(tempJ) + tempC;
            tempC = (l >> CRYPTO_NUMBER_26) + (m >> CRYPTO_NUMBER_13) + xh * h;
            w.array = Benchmark.insertValue(w.array, l & CRYPTO_NUMBER_0X3FFFFFF, tempJ);
            tempI += 1;
            tempJ += 1;
            tempN -= 1;
        }
        return tempC;
    };

    public static AmBlock aM;

    // am3/28 is best for SM, Rhino, but am4/26 is best for v8.
    // Kestrel (Opera 9.5) gets its best result with am4/26.
    // IE7 does 9% better with am3/28 than with am4/26.
    // Firefox (SM) gets 10% faster with am3/28 than with am4/26.
    public static void setupEngine(AmBlock fn, int bits) {
        aM = fn;
        dbits = bits;
        bIDB = dbits;
        bIDM = (1 << dbits) - 1;
        bIDV = 1 << dbits;

        bIFP = CRYPTO_NUMBER_52;
        bIFV = (long) Math.pow(CRYPTO_NUMBER_2, bIFP);
        bIF1 = bIFP - dbits;
        bIF2 = CRYPTO_NUMBER_2 * dbits - bIFP;
    }

    // Digit conversions
    public static String bIRM = "0123456789abcdefghijklmnopqrstuvwxyz";
    public static ArrayList<Integer> bIRC = new ArrayList<>();

    public static void initBIRC() {
        int rr;
        rr = "0".codePointAt(0);
        for (int vv = 0; vv <= CRYPTO_NUMBER_9; ++vv) {
            bIRC = Benchmark.insertValue(bIRC, vv, rr);
            rr += 1;
        }
        rr = "a".codePointAt(0);
        for (int vv = CRYPTO_NUMBER_10; vv < CRYPTO_NUMBER_36; ++vv) {
            bIRC = Benchmark.insertValue(bIRC, vv, rr);
            rr += 1;
        }
        rr = "A".codePointAt(0);
        for (int vv = CRYPTO_NUMBER_10; vv < CRYPTO_NUMBER_36; ++vv) {
            bIRC = Benchmark.insertValue(bIRC, vv, rr);
            rr += 1;
        }
    }
}

class BigInteger {
    public static BigInteger one = BigInteger.nbv(1);
    public static BigInteger zero = BigInteger.nbv(0);
    public ArrayList<Integer> array = new ArrayList<>();
    public int t = 0;
    public int s = 0;

    // (public) Constructor
    BigInteger() {
        this(null, null, null);
    }

    BigInteger(Object a) {
        this(a, null, null);
    }

    BigInteger(Object a, Object b) {
        this(a, b, null);
    }

    BigInteger(Object a, Object b, Object c) {
        if (a != null) {
            if (a instanceof Integer) {
                this.fromNumber((int) a, b, c);
            } else if (b == null && !(a instanceof String)) {
                this.fromString(a, Crypto.CRYPTO_NUMBER_256);
            } else {
                this.fromString(a, (int) b);
            }
        }
    }

    // return new, unset BigInteger
    public static BigInteger nbi() {
        return new BigInteger();
    }

    // return bigint initialized to value
    public static BigInteger nbv(int i) {
        BigInteger r = BigInteger.nbi();
        r.fromInt(i);
        return r;
    }

    public String int2char(int n) {
        return String.valueOf(Crypto.bIRM.charAt(n));
    }

    public int intAt(String s, int i) {
        Integer c = Crypto.bIRC.get(s.codePointAt(i));
        return c == null ? -1 : c;
    }

    // (protected) copy this to r
    public void copyTo(BigInteger r) {
        int i = this.t - 1;
        while (i >= 0) {
            r.array = Benchmark.insertValue(r.array, this.array.get(i), i);
            i -= 1;
        }
        r.t = this.t;
        r.s = this.s;
    }

    // (protected) set from integer value x, -DV <= x < DV
    public void fromInt(int x) {
        this.t = 1;
        this.s = x < 0 ? -1 : 0;
        if (x > 0) {
            this.array = Benchmark.insertValue(this.array, x, 0);
        } else if (x < -1) {
            this.array = Benchmark.insertValue(this.array, x + Crypto.dv, 0);
        } else {
            this.t = 0;
        }
    }

    // (protected) set from string and radix
    public void fromString(Object s, int b) {
        int k;
        if (b == Crypto.CRYPTO_NUMBER_16) {
            k = Crypto.CRYPTO_NUMBER_4;
        } else if (b == Crypto.CRYPTO_NUMBER_8) {
            k = Crypto.CRYPTO_NUMBER_3;
        } else if (b == Crypto.CRYPTO_NUMBER_256) {
            k = Crypto.CRYPTO_NUMBER_8; // byte array
        } else if (b == Crypto.CRYPTO_NUMBER_2) {
            k = 1;
        } else if (b == Crypto.CRYPTO_NUMBER_32) {
            k = Crypto.CRYPTO_NUMBER_5;
        } else if (b == Crypto.CRYPTO_NUMBER_4) {
            k = Crypto.CRYPTO_NUMBER_2;
        } else {
            this.fromRadix((String) s, b);
            return;
        }
        this.t = 0;
        this.s = 0;
        int i;
        boolean mi = false;
        int sh = 0;
        if (k == Crypto.CRYPTO_NUMBER_8) {
            ArrayList<Integer> tempS = (ArrayList<Integer>) s;
            i = tempS.size();
        } else {
            i = ((String) s).length();
        }
        i -= 1;
        while (i >= 0) {
            int x;
            if (k == Crypto.CRYPTO_NUMBER_8) {
                x = ((ArrayList<Integer>) s).get(i) & Crypto.CRYPTO_NUMBER_0XFF;
            } else {
                x = this.intAt((String) s, i);
            }
            if (x < 0) {
                if (String.valueOf(((String) s).charAt(i)).equals("-")) {
                    mi = true;
                }
                continue;
            }
            mi = false;
            if (sh == 0) {
                this.array = Benchmark.insertValue(this.array, x, this.t);
                this.t += 1;
            } else if (sh + k > Crypto.bIDB) {
                this.array = Benchmark.insertValue(this.array, this.array.get(this.t - 1) | ((x & ((1 << (Crypto.bIDB - sh)) - 1)) << sh), this.t - 1);
                this.array = Benchmark.insertValue(this.array, x >> (Crypto.bIDB - sh), this.t);
                this.t += 1;
            } else {
                this.array = Benchmark.insertValue(this.array, this.array.get(this.t - 1) | (x << sh), this.t - 1);
            }
            sh += k;
            if (sh >= Crypto.bIDB) {
                sh -= Crypto.bIDB;
            }
            i -= 1;
        }
        if (k == Crypto.CRYPTO_NUMBER_8 && (((ArrayList<Integer>) s).get(0) & Crypto.CRYPTO_NUMBER_0X80) != 0) {
            this.s = -1;
            if (sh > 0) {
                this.array.set(this.t - 1, this.array.get(this.t - 1) | ((1 << (Crypto.bIDB - sh)) - 1) << sh);
            }
        }
        this.clamp();
        if (mi) {
            BigInteger.zero.subTo(this, this);
        }
    }

    // (protected) clamp off excess high words
    public void clamp() {
        int c = this.s & Crypto.bIDM;
        while (this.t > 0 && this.array.get(this.t - 1) == c) {
            this.t -= 1;
        }
    }

    // (public) return string representation in given radix
    public String toString(int b) {
        if (this.s < 0) {
            return "-" + this.negate().toString(b);
        }
        int k;
        if (b == Crypto.CRYPTO_NUMBER_16) {
            k = Crypto.CRYPTO_NUMBER_4;
        } else if (b == Crypto.CRYPTO_NUMBER_8) {
            k = Crypto.CRYPTO_NUMBER_3;
        } else if (b == Crypto.CRYPTO_NUMBER_2) {
            k = 1;
        } else if (b == Crypto.CRYPTO_NUMBER_32) {
            k = Crypto.CRYPTO_NUMBER_5;
        } else if (b == Crypto.CRYPTO_NUMBER_4) {
            k = Crypto.CRYPTO_NUMBER_2;
        } else {
            return this.toRadix(b);
        }
        int km = (1 << k) - 1;
        int d;
        boolean m = false;
        String r = "";
        int i = this.t;
        int p = Crypto.bIDB - ((i * Crypto.bIDB) % k);
        if (i > 0) {
            i -= 1;
            d = this.array.get(i) >> p;
            if (p < Crypto.bIDB && d > 0) {
                m = true;
                r = this.int2char(d);
            }
            while (i >= 0) {
                if (p < k) {
                    d = (this.array.get(i) & ((1 << p) - 1)) << (k - p);
                    i -= 1;
                    p += Crypto.bIDB - k;
                    d |= this.array.get(i) >> p;
                } else {
                    p -= k;
                    d = (this.array.get(i) >> p) & km;
                    if (p <= 0) {
                        p += Crypto.bIDB;
                        i -= 1;
                    }
                }
                if (d > 0) {
                    m = true;
                }
                if (m) {
                    r += this.int2char(d);
                }
            }
        }
        return m ? r : "0";
    }

    // (public) -this
    public BigInteger negate() {
        BigInteger r = BigInteger.nbi();
        BigInteger.zero.subTo(this, r);
        return r;
    }

    // (public) |this|
    public BigInteger abs() {
        return this.s < 0 ? this.negate() : this;
    }

    // (public) return + if this > a, - if this < a, 0 if equal
    public int compareTo(BigInteger a) {
        int r = this.s - a.s;
        if (r != 0) {
            return r;
        }
        int i = this.t;
        r = i - a.t;
        if (r != 0) {
            return r;
        }
        i -= 1;
        while (i >= 0) {
            r = this.array.get(i) - a.array.get(i);
            if (r != 0) {
                return r;
            }
            i -= 1;
        }
        return 0;
    }

    // returns bit length of the integer x
    public int nbits(long x) {
        long tempX = x;
        int r = 1;
        long t = tempX >>> Crypto.CRYPTO_NUMBER_16;
        if (t != 0) {
            tempX = t;
            r += Crypto.CRYPTO_NUMBER_16;
        }
        t = tempX >> Crypto.CRYPTO_NUMBER_8;
        if (t != 0) {
            tempX = t;
            r += Crypto.CRYPTO_NUMBER_8;
        }
        t = tempX >> Crypto.CRYPTO_NUMBER_4;
        if (t != 0) {
            tempX = t;
            r += Crypto.CRYPTO_NUMBER_4;
        }
        t = tempX >> Crypto.CRYPTO_NUMBER_2;
        if (t != 0) {
            tempX = t;
            r += Crypto.CRYPTO_NUMBER_2;
        }
        t = tempX >> 1;
        if (t != 0) {
            tempX = t;
            r += 1;
        }
        return r;
    }

    // (public) return the number of bits in "this"
    public int bitLength() {
        if (this.t <= 0) {
            return 0;
        }
        return Crypto.bIDB * (this.t - 1) + this.nbits(this.array.get(this.t - 1) ^ (this.s & Crypto.bIDM));
    }

    // (protected) r = this << n*DB
    public void dlShiftTo(int n, BigInteger r) {
        int i = this.t - 1;
        while (i >= 0) {
            r.array = Benchmark.insertValue(r.array, this.array.get(i), i + n);
            i -= 1;
        }
        i = n - 1;
        while (i >= 0) {
            r.array = Benchmark.insertValue(r.array, 0, i);
            i -= 1;
        }
        r.t = this.t + n;
        r.s = this.s;
    }

    // (protected) r = this >> n*DB
    public void drShiftTo(int n, BigInteger r) {
        int i = n;
        while (i < this.t) {
            r.array = Benchmark.insertValue(r.array, this.array.get(i), i - n);
            i += 1;
        }
        r.t = Math.max(this.t - n, 0);
        r.s = this.s;
    }

    // (protected) r = this << n
    public void lShiftTo(int n, BigInteger r) {
        int bs = n % Crypto.bIDB;
        int cbs = Crypto.bIDB - bs;
        int bm = (1 << cbs) - 1;
        int ds = (int) Math.floor((double) n / Crypto.bIDB);
        int c = (this.s << bs) & Crypto.bIDM;
        int i = this.t - 1;
        while (i >= 0) {
            r.array = Benchmark.insertValue(r.array, (this.array.get(i) >> cbs) | c, i + ds + 1);
            c = (this.array.get(i) & bm) << bs;
            i -= 1;
        }
        i = ds - 1;
        while (i >= 0) {
            r.array = Benchmark.insertValue(r.array, 0, i);
            i -= 1;
        }
        r.array = Benchmark.insertValue(r.array, c, ds);
        r.t = this.t + ds + 1;
        r.s = this.s;
        r.clamp();
    }

    // (protected) r = this >> n
    public void rShiftTo(int n, BigInteger r) {
        r.s = this.s;
        int ds = (int) Math.floor((double) n / Crypto.bIDB);
        if (ds >= this.t) {
            r.t = 0;
            return;
        }
        int bs = n % Crypto.bIDB;
        int cbs = Crypto.bIDB - bs;
        int bm = (1 << bs) - 1;
        r.array = Benchmark.insertValue(r.array, this.array.get(ds) >> bs, 0);
        for (int i = ds + 1; i < this.t; ++i) {
            r.array = Benchmark.insertValue(r.array, r.array.get(i - ds - 1) | ((this.array.get(i) & bm) << cbs), i - ds - 1);
            r.array = Benchmark.insertValue(r.array, this.array.get(i) >> bs, i - ds);
        }
        if (bs > 0) {
            r.array = Benchmark.insertValue(r.array, r.array.get(this.t - ds - 1) | ((this.s & bm) << cbs), this.t - ds - 1);
        }
        r.t = this.t - ds;
        r.clamp();
    }

    // (protected) r = this - a
    public void subTo(BigInteger a, BigInteger r) {
        int i = 0;
        int c = 0;
        int m = Math.min(a.t, this.t);
        while (i < m) {
            c += this.array.get(i) - a.array.get(i);
            r.array = Benchmark.insertValue(r.array, c & Crypto.bIDM, i);
            c >>= Crypto.bIDB;
            i += 1;
        }
        if (a.t < this.t) {
            c -= a.s;
            while (i < this.t) {
                c += this.array.get(i);
                r.array = Benchmark.insertValue(r.array, c & Crypto.bIDM, i);
                c >>= Crypto.bIDB;
                i += 1;
            }
            c += this.s;
        } else {
            c += this.s;
            while (i < a.t) {
                c -= a.array.get(i);
                r.array = Benchmark.insertValue(r.array, c & Crypto.bIDM, i);
                c >>= Crypto.bIDB;
                i += 1;
            }
            c -= a.s;
        }
        r.s = c < 0 ? -1 : 0;
        if (c < -1) {
            r.array = Benchmark.insertValue(r.array, Crypto.bIDV + c, i);
            i += 1;
        } else if (c > 0) {
            r.array = Benchmark.insertValue(r.array, c, i);
            i += 1;
        }
        r.t = i;
        r.clamp();
    }

    // (protected) r = this * a, r !== this,a (HAC 14.12)
    // "this" should be the larger one if appropriate.
    public void multiplyTo(BigInteger a, BigInteger r) {
        BigInteger x = this.abs();
        BigInteger y = a.abs();
        int i = x.t;
        r.t = i + y.t;
        i -= 1;
        while (i >= 0) {
            r.array = Benchmark.insertValue(r.array, 0, i);
            i -= 1;
        }
        for (i = 0; i < y.t; ++i) {
            int value = x.am(0, y.array.get(i), r, i, 0, x.t);
            r.array = Benchmark.insertValue(r.array, value, i + x.t);
        }
        r.s = 0;
        r.clamp();
        if (this.s != a.s) {
            BigInteger.zero.subTo(r, r);
        }
    }

    // (protected) r = this^2, r !== this (HAC 14.16)
    public void squareTo(BigInteger r) {
        BigInteger x = this.abs();
        r.t = Crypto.CRYPTO_NUMBER_2 * x.t;
        int i = r.t - 1;
        while (i >= 0) {
            r.array = Benchmark.insertValue(r.array, 0, i);
            i -= 1;
        }
        i = 0;
        while (i < x.t - 1) {
            int c = x.am(i, x.array.get(i), r, Crypto.CRYPTO_NUMBER_2 * i, 0, 1);
            int value = r.array.get(i + x.t) + x.am(i + 1, Crypto.CRYPTO_NUMBER_2 * x.array.get(i), r, Crypto.CRYPTO_NUMBER_2 * i + 1, c, x.t - i - 1);
            r.array = Benchmark.insertValue(r.array, value, i + x.t);
            if (r.array.get(i + x.t) >= Crypto.bIDV) {
                r.array = Benchmark.insertValue(r.array, r.array.get(i + x.t) - Crypto.bIDV, i + x.t);
                r.array = Benchmark.insertValue(r.array, 1, i + x.t + 1);
            }
            i += 1;
        }
        if (r.t > 0) {
            int value = r.array.get(r.t - 1) + x.am(i, x.array.get(i), r, Crypto.CRYPTO_NUMBER_2 * i, 0, 1);
            r.array = Benchmark.insertValue(r.array, value, r.t - 1);
        }
        r.s = 0;
        r.clamp();
    }

    // (protected) divide this by m, quotient and remainder to q, r (HAC 14.20)
    // r !== q, this !== m.  q or r may be null.
    public void divRemTo(BigInteger m, BigInteger q, BigInteger r) {
        BigInteger pm = m.abs();
        if (pm.t <= 0) {
            return;
        }
        BigInteger pt = this.abs();
        if (pt.t < pm.t) {
            if (q != null) {
                q.fromInt(0);
            }
            if (r != null) {
                this.copyTo(r);
            }
            return;
        }
        if (r == null) {
            r = BigInteger.nbi();
        }
        BigInteger y = BigInteger.nbi();
        int ts = this.s;
        int ms = m.s;
        int nsh = Crypto.bIDB - this.nbits(pm.array.get(pm.t - 1)); // normalize modulus
        if (nsh > 0) {
            pm.lShiftTo(nsh, y);
            pt.lShiftTo(nsh, r);
        } else {
            pm.copyTo(y);
            pt.copyTo(r);
        }
        int ys = y.t;
        int y0 = y.array.get(ys - 1);
        if (y0 == 0) {
            return;
        }
        long yt = (long) y0 * (1L << Crypto.bIF1) + (ys > 1 ? y.array.get(ys - Crypto.CRYPTO_NUMBER_2) >> Crypto.bIF2 : 0);
        double d1 = (double) Crypto.bIFV / yt;
        double d2 = (double) (1 << Crypto.bIF1) / yt;
        int e = 1 << Crypto.bIF2;
        int i = r.t;
        int j = i - ys;
        BigInteger t = q == null ? BigInteger.nbi() : q;
        y.dlShiftTo(j, t);
        if (r.compareTo(t) >= 0) {
            r.array = Benchmark.insertValue(r.array, 1, r.t);
            r.t += 1;
            r.subTo(t, r);
        }
        BigInteger.one.dlShiftTo(ys, t);
        t.subTo(y, y); // "negative" y so we can replace sub with am later
        while (y.t < ys) {
            y.array = Benchmark.insertValue(y.array, 0, y.t);
            y.t += 1;
        }
        j -= 1;
        while (j >= 0) {
            i -= 1; // Estimate quotient digit
            int qd = r.array.get(i) == y0 ? Crypto.bIDM : (int) Math.floor(r.array.get(i) * d1 + (r.array.get(i - 1) + e) * d2);
            int value = r.array.get(i) + y.am(0, qd, r, j, 0, ys);
            r.array = Benchmark.insertValue(r.array, value, i);
            if (r.array.get(i) < qd) {
                y.dlShiftTo(j, t); // Try it out
                r.subTo(t, r);
                qd -= 1;
                while (r.array.get(i) < qd) {
                    r.subTo(t, r);
                    qd -= 1;
                }
            }
            j -= 1;
        }
        if (q != null) {
            r.drShiftTo(ys, q);
            if (ts != ms) {
                BigInteger.zero.subTo(q, q);
            }
        }
        r.t = ys;
        r.clamp();
        if (nsh > 0) {
            r.rShiftTo(nsh, r);
        } // Denormalize remainder
        if (ts < 0) {
            BigInteger.zero.subTo(r, r);
        }
    }

    // (public) this mod a
    public BigInteger mod(BigInteger a) {
        BigInteger r = BigInteger.nbi();
        this.abs().divRemTo(a, null, r);
        if (this.s < 0 && r.compareTo(BigInteger.zero) > 0) {
            a.subTo(r, r);
        }
        return r;
    }

    public int invDigit() {
        if (this.t < 1) {
            return 0;
        }
        int x = this.array.get(0);
        if ((x & 1) == 0) {
            return 0;
        }
        int y = x & Crypto.CRYPTO_NUMBER_3; // y === 1/x mod 2^2
        y = (y * (Crypto.CRYPTO_NUMBER_2 - (x & Crypto.CRYPTO_NUMBER_0XF) * y)) & Crypto.CRYPTO_NUMBER_0XF; // y === 1/x mod 2^4
        y = (y * (Crypto.CRYPTO_NUMBER_2 - (x & Crypto.CRYPTO_NUMBER_0XFF) * y)) & Crypto.CRYPTO_NUMBER_0XFF; // y === 1/x mod 2^8
        y = (y * (Crypto.CRYPTO_NUMBER_2 - (((x & Crypto.CRYPTO_NUMBER_0XFFFF) * y) & Crypto.CRYPTO_NUMBER_0XFFFF))) & Crypto.CRYPTO_NUMBER_0XFFFF; // y === 1/x mod 2^16
        // last step - calculate inverse mod DV directly;
        // assumes 16 < DB <= 32 and assumes ability to handle 48-bit ints
        y = (y * (Crypto.CRYPTO_NUMBER_2 - ((x * y) % Crypto.bIDV))) % Crypto.bIDV; // y === 1/x mod 2^dbits
        // we really want the negative inverse, and -DV < y < DV
        return y > 0 ? Crypto.bIDV - y : -y;
    }

    // (protected) true iff this is even
    public boolean isEven() {
        return (this.t > 0 ? this.array.get(0) & 1 : this.s) == 0;
    }

    // (protected) this^e, e < 2^32, doing sqr and mul with "r" (HAC 14.79)
    public BigInteger exp(long e, ConvertProtocol z) {
        if (e > Crypto.CRYPTO_NUMBER_0XFFFFFFFF || e < 1) {
            return BigInteger.one;
        }
        BigInteger r = BigInteger.nbi();
        BigInteger r2 = BigInteger.nbi();
        BigInteger g = z.convert(this);
        int i = this.nbits(e) - 1 - 1;
        g.copyTo(r);
        while (i >= 0) {
            z.sqrTo(r, r2);
            if ((e & (1L << i)) > 0) {
                z.mulTo(r2, g, r);
            } else {
                BigInteger t = r;
                r = r2;
                r2 = t;
            }
            i -= 1;
        }
        return z.revert(r);
    }

    // (public) this^e % m, 0 <= e < 2^32
    public BigInteger modPowInt(int e, BigInteger m) {
        ConvertProtocol z;
        if (e < Crypto.CRYPTO_NUMBER_256 || m.isEven()) {
            z = new Classic(m);
        } else {
            z = new Montgomery(m);
        }
        return this.exp(e, z);
    }

    // (public)
    public BigInteger clones() {
        BigInteger r = BigInteger.nbi();
        this.copyTo(r);
        return r;
    }

    // (public) return value as integer
    public int intValue() {
        if (this.s < 0) {
            if (this.t == 1) {
                return this.array.get(0) - Crypto.bIDV;
            } else if (this.t == 0) {
                return -1;
            }
        } else if (this.t == 1) {
            return this.array.get(0);
        } else if (this.t == 0) {
            return 0;
        }
        // assumes 16 < DB < 32
        return ((this.array.get(1) & ((1 << (Crypto.CRYPTO_NUMBER_32 - Crypto.bIDB)) - 1)) << Crypto.bIDB) | this.array.get(0);
    }

    // (public) return value as byte
    public int byteValue() {
        return this.t == 0 ? this.s : (this.array.get(0) << Crypto.CRYPTO_NUMBER_24) >> Crypto.CRYPTO_NUMBER_24;
    }

    // (public) return value as short (assumes DB>=16)
    public int shortValue() {
        return this.t == 0 ? this.s : (this.array.get(0) << Crypto.CRYPTO_NUMBER_16) >> Crypto.CRYPTO_NUMBER_16;
    }

    // (protected) return x s.t. r^x < DV
    public int chunkSize(int r) {
        return (int) Math.floor((Math.log(2) * Crypto.bIDB) / Math.log(r));
    }

    // (public) 0 if this === 0, 1 if this > 0
    public int signum() {
        if (this.s < 0) {
            return -1;
        } else if (this.t <= 0 || (this.t == 1 && this.array.get(0) <= 0)) {
            return 0;
        } else {
            return 1;
        }
    }

    // (protected) convert to radix string
    public String toRadix(Integer b) {
        int tempB = b == null ? Crypto.CRYPTO_NUMBER_10 : b;
        if (this.signum() == 0 || tempB < Crypto.CRYPTO_NUMBER_2 || tempB > Crypto.CRYPTO_NUMBER_36) {
            return "0";
        }
        int cs = this.chunkSize(tempB);
        int a = (int) Math.pow(tempB, cs);
        BigInteger d = nbv(a);
        BigInteger y = nbi();
        BigInteger z = nbi();
        String r = "";
        this.divRemTo(d, y, z);
        while (y.signum() > 0) {
            String str = Integer.toString(a + z.intValue(), tempB);
            r = str.substring(1) + r;
            y.divRemTo(d, y, z);
        }
        return Integer.toString(z.intValue(), tempB) + r;
    }

    // (protected) convert from radix string
    public void fromRadix(String s, Integer b) {
        this.fromInt(0);
        int tempB = b == null ? Crypto.CRYPTO_NUMBER_10 : b;
        int cs = this.chunkSize(tempB);
        int d = (int) Math.pow(tempB, cs);
        boolean mi = false;
        int j = 0;
        int w = 0;
        for (int i = 0; i < s.length(); ++i) {
            int x = this.intAt(s, i);
            if (x < 0) {
                if (String.valueOf(s.charAt(i)).equals("-") && this.signum() == 0) {
                    mi = true;
                }
                continue;
            }
            w = tempB * w + x;
            j += 1;
            if (j >= cs) {
                this.dMultiply(d);
                this.dAddOffset(w, 0);
                j = 0;
                w = 0;
            }
        }
        if (j > 0) {
            this.dMultiply((int) Math.pow(tempB, j));
            this.dAddOffset(w, 0);
        }
        if (mi) {
            BigInteger.zero.subTo(this, this);
        }
    }

    // (protected) alternate constructor
    public void fromNumber(int a, Object b, Object c) {
        if (b instanceof Integer) {
            // new BigInteger(int,int,RNG)
            if (a < Crypto.CRYPTO_NUMBER_2) {
                this.fromInt(1);
            } else {
                this.fromNumber(a, c, null);
                if (!this.testBit(a - 1)) {
                    // force MSB set
                    this.bitwiseTo(BigInteger.one.shiftLeft(a - 1), this.opOr, this);
                }
                if (this.isEven()) {
                    this.dAddOffset(1, 0); // force odd
                }
                while (!this.isProbablePrime((int) b)) {
                    this.dAddOffset(Crypto.CRYPTO_NUMBER_2, 0);
                    if (this.bitLength() > a) {
                        this.subTo(BigInteger.one.shiftLeft(a - 1), this);
                    }
                }
            }
        } else {
            // new BigInteger(int,RNG)
            ArrayList<Integer> x = new ArrayList<>((a >> Crypto.CRYPTO_NUMBER_3) + 1);
            int t = a & Crypto.CRYPTO_NUMBER_7;
            ((SecureRandom) b).nextBytes(x);
            if (t > 0) {
                x = Benchmark.insertValue(x, x.get(0) & ((1 << t) - 1), 0);
            } else {
                x = Benchmark.insertValue(x, 0, 0);
            }
            this.fromString(x, Crypto.CRYPTO_NUMBER_256);
        }
    }

    // (public) convert to bigendian byte array
    public ArrayList<Integer> toByteArray() {
        int i = this.t;
        ArrayList<Integer> r = new ArrayList<>();
        Benchmark.insertValue(r, this.s, 0);
        int p = Crypto.bIDB - ((i * Crypto.bIDB) % Crypto.CRYPTO_NUMBER_8);
        int d;
        int k = 0;
        if (i > 0) {
            i -= 1;
            d = this.array.get(i) >> p;
            if (p < Crypto.bIDB && d != (this.s & Crypto.bIDM) >> p) {
                r = Benchmark.insertValue(r, d | (this.s << (Crypto.bIDB - p)), k);
                k += 1;
            }
            while (i >= 0) {
                if (p < Crypto.CRYPTO_NUMBER_8) {
                    d = (this.array.get(i) & ((1 << p) - 1)) << (Crypto.CRYPTO_NUMBER_8 - p);
                    i -= 1;
                    p += Crypto.bIDB - Crypto.CRYPTO_NUMBER_8;
                    d |= this.array.get(i) >> p;
                } else {
                    p -= Crypto.CRYPTO_NUMBER_8;
                    d = (this.array.get(i) >> p) & Crypto.CRYPTO_NUMBER_0XFF;
                    if (p <= 0) {
                        p += Crypto.bIDB;
                        i -= 1;
                    }
                }
                if ((d & Crypto.CRYPTO_NUMBER_0X80) != 0) {
                    d |= -Crypto.CRYPTO_NUMBER_256;
                }
                if (k == 0 && (this.s & Crypto.CRYPTO_NUMBER_0X80) != (d & Crypto.CRYPTO_NUMBER_0X80)) {
                    k += 1;
                }
                if (k > 0 || d != this.s) {
                    r = Benchmark.insertValue(r, d, k);
                    k += 1;
                }
            }
        }
        return r;
    }

    public boolean bnEquals(BigInteger a) {
        return this.compareTo(a) == 0;
    }

    public BigInteger bnMin(BigInteger a) {
        return this.compareTo(a) < 0 ? this : a;
    }

    public BigInteger bnMax(BigInteger a) {
        return this.compareTo(a) > 0 ? this : a;
    }

    // (protected) r = this op a (bitwise)
    public void bitwiseTo(BigInteger a, OpBlock op, BigInteger r) {
        int f;
        int m = Math.min(a.t, this.t);
        for (int i = 0; i < m; ++i) {
            r.array = Benchmark.insertValue(r.array, op.call(this.array.get(i), a.array.get(i)), i);
        }
        if (a.t < this.t) {
            f = a.s & Crypto.bIDM;
            for (int i = m; i < this.t; ++i) {
                r.array = Benchmark.insertValue(r.array, op.call(this.array.get(i), f), i);
            }
            r.t = this.t;
        } else {
            f = this.s & Crypto.bIDM;
            for (int i = m; i < a.t; ++i) {
                r.array = Benchmark.insertValue(r.array, op.call(f, a.array.get(i)), i);
            }
            r.t = a.t;
        }
        r.s = op.call(this.s, a.s);
        r.clamp();
    }

    // (public) this & a
    public OpBlock opAnd = (int x, int y) -> {
        return x & y;
    };

    public BigInteger bnAnd(BigInteger a) {
        BigInteger r = BigInteger.nbi();
        this.bitwiseTo(a, this.opAnd, r);
        return r;
    }

    // (public) this | a
    public OpBlock opOr = (int x, int y) -> {
        return x | y;
    };

    public BigInteger bnOr(BigInteger a) {
        BigInteger r = BigInteger.nbi();
        this.bitwiseTo(a, this.opOr, r);
        return r;
    }

    // (public) this ^ a
    public OpBlock opXor = (int x, int y) -> {
        return x ^ y;
    };

    public BigInteger bnXor(BigInteger a) {
        BigInteger r = BigInteger.nbi();
        this.bitwiseTo(a, this.opXor, r);
        return r;
    }

    // (public) this & ~a
    public OpBlock opAndnot = (int x, int y) -> {
        return x & ~y;
    };

    public BigInteger bnAndNot(BigInteger a) {
        BigInteger r = BigInteger.nbi();
        this.bitwiseTo(a, this.opAndnot, r);
        return r;
    }

    // (public) ~this
    public BigInteger bnNot() {
        BigInteger r = BigInteger.nbi();
        for (int i = 0; i < this.t; ++i) {
            r.array = Benchmark.insertValue(r.array, Crypto.bIDM & ~this.array.get(i), i);
        }
        r.t = this.t;
        r.s = ~this.s;
        return r;
    }

    // (public) this << n
    public BigInteger shiftLeft(int n) {
        BigInteger r = BigInteger.nbi();
        if (n < 0) {
            this.rShiftTo(-n, r);
        } else {
            this.lShiftTo(n, r);
        }
        return r;
    }

    // (public) this >> n
    public BigInteger shiftRight(int n) {
        BigInteger r = BigInteger.nbi();
        if (n < 0) {
            this.lShiftTo(-n, r);
        } else {
            this.rShiftTo(n, r);
        }
        return r;
    }

    // return index of lowest 1-bit in x, x < 2^31
    public int lbit(int x) {
        int tempX = x;
        if (tempX == 0) {
            return -1;
        }
        int r = 0;
        if ((tempX & Crypto.CRYPTO_NUMBER_0XFFFF) == 0) {
            tempX >>= Crypto.CRYPTO_NUMBER_16;
            r += Crypto.CRYPTO_NUMBER_16;
        }
        if ((tempX & Crypto.CRYPTO_NUMBER_0XFF) == 0) {
            tempX >>= Crypto.CRYPTO_NUMBER_8;
            r += Crypto.CRYPTO_NUMBER_8;
        }
        if ((tempX & Crypto.CRYPTO_NUMBER_0XF) == 0) {
            tempX >>= Crypto.CRYPTO_NUMBER_4;
            r += Crypto.CRYPTO_NUMBER_4;
        }
        if ((tempX & Crypto.CRYPTO_NUMBER_3) == 0) {
            tempX >>= Crypto.CRYPTO_NUMBER_2;
            r += Crypto.CRYPTO_NUMBER_2;
        }
        if ((tempX & 1) == 0) {
            r += 1;
        }
        return r;
    }

    // (public) returns index of lowest 1-bit (or -1 if none)
    public int getLowestSetBit() {
        for (int i = 0; i < this.t; ++i) {
            if (this.array.get(i) != 0) {
                return i * Crypto.bIDB + this.lbit(this.array.get(i));
            }
        }
        if (this.s < 0) {
            return this.t * Crypto.bIDB;
        }
        return -1;
    }

    // return number of 1 bits in x
    public int cbit(int x) {
        int r = 0;
        int tepmX = x;
        while (tepmX != 0) {
            tepmX &= tepmX - 1;
            r += 1;
        }
        return r;
    }

    // (public) return number of set bits
    public int bitCount() {
        int r = 0;
        int x = this.s & Crypto.bIDM;
        for (int i = 0; i < this.t; ++i) {
            r += this.cbit(this.array.get(i) ^ x);
        }
        return r;
    }

    // (public) true iff nth bit is set
    public boolean testBit(int n) {
        int j = (int) Math.floor((double) n / Crypto.bIDB);
        if (j >= this.t) {
            return this.s != 0;
        }
        return (this.array.get(j) & (1 << n % Crypto.bIDB)) != 0;
    }

    // (protected) this op (1<<n)
    public BigInteger changeBit(int n, OpBlock op) {
        BigInteger r = BigInteger.one.shiftLeft(n);
        this.bitwiseTo(r, op, r);
        return r;
    }

    // (public) this | (1<<n)
    public BigInteger setBit(int n) {
        return this.changeBit(n, this.opOr);
    }

    // (public) this & ~(1<<n)
    public BigInteger clearBit(int n) {
        return this.changeBit(n, this.opAndnot);
    }

    // (public) this ^ (1<<n)
    public BigInteger flipBit(int n) {
        return this.changeBit(n, this.opXor);
    }

    // (protected) r = this + a
    public void addTo(BigInteger a, BigInteger r) {
        int i = 0;
        int c = 0;
        int m = Math.min(a.t, this.t);
        while (i < m) {
            c += this.array.get(i) + a.array.get(i);
            r.array = Benchmark.insertValue(r.array, c & Crypto.bIDM, i);
            c >>= Crypto.bIDB;
            i += 1;
        }
        if (a.t < this.t) {
            c += a.s;
            while (i < this.t) {
                c += this.array.get(i);
                r.array = Benchmark.insertValue(r.array, c & Crypto.bIDM, i);
                c >>= Crypto.bIDB;
                i += 1;
            }
            c += this.s;
        } else {
            c += this.s;
            while (i < a.t) {
                c += a.array.get(i);
                r.array = Benchmark.insertValue(r.array, c & Crypto.bIDM, i);
                c >>= Crypto.bIDB;
                i += 1;
            }
            c += a.s;
        }
        r.s = c < 0 ? -1 : 0;
        if (c > 0) {
            r.array = Benchmark.insertValue(r.array, c, i);
            i += 1;
        } else if (c < -1) {
            r.array = Benchmark.insertValue(r.array, Crypto.bIDV + c, i);
            i += 1;
        }
        r.t = i;
        r.clamp();
    }

    // (public) this + a
    public BigInteger add(BigInteger a) {
        BigInteger r = BigInteger.nbi();
        this.addTo(a, r);
        return r;
    }

    // (public) this - a
    public BigInteger subtract(BigInteger a) {
        BigInteger r = BigInteger.nbi();
        this.subTo(a, r);
        return r;
    }

    // (public) this * a
    public BigInteger multiply(BigInteger a) {
        BigInteger r = BigInteger.nbi();
        this.multiplyTo(a, r);
        return r;
    }

    // (public) this / a
    public BigInteger divide(BigInteger a) {
        BigInteger r = BigInteger.nbi();
        BigInteger temp = null;
        this.divRemTo(a, r, temp);
        return r;
    }

    // (public) this % a
    public BigInteger remainder(BigInteger a) {
        BigInteger r = BigInteger.nbi();
        this.divRemTo(a, null, r);
        return r;
    }

    // (public) [this/a,this%a]
    public ArrayList<BigInteger> divideAndRemainder(BigInteger a) {
        BigInteger q = BigInteger.nbi();
        BigInteger r = BigInteger.nbi();
        this.divRemTo(a, q, r);
        return (ArrayList<BigInteger>) Arrays.asList(q, r);
    }

    // (protected) this *= n, this >= 0, 1 < n < DV
    public void dMultiply(int n) {
        int value = this.am(0, n - 1, this, 0, 0, this.t);
        this.array = Benchmark.insertValue(this.array, value, this.t);
        this.t += 1;
        this.clamp();
    }

    // (protected) this += n << w words, this >= 0
    public void dAddOffset(int n, int w) {
        int tempW = w;
        while (this.t <= tempW) {
            this.array = Benchmark.insertValue(this.array, 0, this.t);
            this.t += 1;
        }
        this.array = Benchmark.insertValue(this.array, this.array.get(tempW) + n, tempW);
        while (this.array.get(tempW) >= Crypto.bIDV) {
            this.array = Benchmark.insertValue(this.array, this.array.get(tempW) - Crypto.bIDV, tempW);
            tempW += 1;
            if (tempW >= this.t) {
                this.array = Benchmark.insertValue(this.array, 0, this.t);
                this.t += 1;
            }
            this.array = Benchmark.insertValue(this.array, this.array.get(tempW) + 1, tempW);
        }
    }

    // (public) this^e
    public BigInteger bnPow(int e) {
        return this.exp(e, new NullExp());
    }

    // (protected) r = lower n words of "this * a", a.t <= n
    // "this" should be the larger one if appropriate.
    public void multiplyLowerTo(BigInteger a, int n, BigInteger r) {
        int i = Math.min(this.t + a.t, n);
        r.s = 0; // assumes a,this >= 0
        r.t = i;
        while (i > 0) {
            i -= 1;
            r.array = Benchmark.insertValue(r.array, 0, i);
        }
        while (i < r.t - this.t) {
            int value = this.am(0, a.array.get(i), r, i, 0, this.t);
            r.array = Benchmark.insertValue(r.array, value, i + this.t);
            i += 1;
        }
        for (int j = Math.min(a.t, n); i < j; ++i) {
            this.am(0, a.array.get(i), r, i, 0, n - i);
        }
        r.clamp();
    }

    // (protected) r = "this * a" without lower n words, n > 0
    // "this" should be the larger one if appropriate.
    public void multiplyUpperTo(BigInteger a, int n, BigInteger r) {
        int tempN = n - 1;
        r.t = this.t + a.t - tempN;
        int i = r.t - 1;
        r.s = 0; // assumes a,this >= 0
        while (i >= 0) {
            r.array = Benchmark.insertValue(r.array, 0, i);
            i -= 1;
        }
        for (i = Math.max(tempN - this.t, 0); i < a.t; ++i) {
            int value = this.am(tempN - i, a.array.get(i), r, 0, 0, this.t + i - tempN);
            r.array = Benchmark.insertValue(r.array, value, this.t + i - tempN);
        }
        r.clamp();
        r.drShiftTo(1, r);
    }

    // (public) this^e % m (HAC 14.85)
    public BigInteger modPow(BigInteger e, BigInteger m) {
        int i = e.bitLength();
        int k;
        BigInteger r = BigInteger.nbv(1);
        ConvertProtocol z;
        if (i <= 0) {
            return r;
        } else if (i < Crypto.CRYPTO_NUMBER_18) {
            k = 1;
        } else if (i < Crypto.CRYPTO_NUMBER_48) {
            k = Crypto.CRYPTO_NUMBER_3;
        } else if (i < Crypto.CRYPTO_NUMBER_144) {
            k = Crypto.CRYPTO_NUMBER_4;
        } else if (i < Crypto.CRYPTO_NUMBER_768) {
            k = Crypto.CRYPTO_NUMBER_5;
        } else {
            k = Crypto.CRYPTO_NUMBER_6;
        }
        if (i < Crypto.CRYPTO_NUMBER_8) {
            z = new Classic(m);
        } else if (m.isEven()) {
            z = new Barrett(m);
        } else {
            z = new Montgomery(m);
        }
        ArrayList<BigInteger> g = new ArrayList<>();
        int n = Crypto.CRYPTO_NUMBER_3;
        int k1 = k - 1;
        int km = (1 << k) - 1;
        g = Benchmark.insertBigIntegerValue(g, z.convert(this), 1);
        if (k > 1) {
            BigInteger g2 = BigInteger.nbi();
            z.sqrTo(g.get(1), g2);
            while (n <= km) {
                g = Benchmark.insertBigIntegerValue(g, BigInteger.nbi(), n);
                z.mulTo(g2, g.get(n - Crypto.CRYPTO_NUMBER_2), g.get(n));
                n += Crypto.CRYPTO_NUMBER_2;
            }
        }
        int j = e.t - 1;
        int w;
        boolean is1 = true;
        BigInteger r2 = BigInteger.nbi();
        BigInteger t;
        i = this.nbits(e.array.get(j)) - 1;
        while (j >= 0) {
            if (i >= k1) {
                w = (e.array.get(j) >> (i - k1)) & km;
            } else {
                w = (e.array.get(j) & ((1 << (i + 1)) - 1)) << (k1 - i);
                if (j > 0) {
                    w |= e.array.get(j - 1) >> (Crypto.bIDB + i - k1);
                }
            }
            n = k;
            while ((w & 1) == 0) {
                w >>= 1;
                n -= 1;
            }
            i -= n;
            if (i < 0) {
                i += Crypto.bIDB;
                j -= 1;
            }
            if (is1) {
                // ret == 1, don't bother squaring or multiplying it
                g.get(w).copyTo(r);
                is1 = false;
            } else {
                while (n > 1) {
                    z.sqrTo(r, r2);
                    z.sqrTo(r2, r);
                    n -= Crypto.CRYPTO_NUMBER_2;
                }
                if (n > 0) {
                    z.sqrTo(r, r2);
                } else {
                    t = r;
                    r = r2;
                    r2 = t;
                }
                z.mulTo(r2, g.get(w), r);
            }
            while (j >= 0 && (e.array.get(j) & (1 << i)) == 0) {
                z.sqrTo(r, r2);
                t = r;
                r = r2;
                r2 = t;
                i -= 1;
                if (i < 0) {
                    i = Crypto.bIDB - 1;
                    j -= 1;
                }
            }
        }
        return z.revert(r);
    }

    // (public) gcd(this,a) (HAC 14.54)
    public BigInteger gcd(BigInteger a) {
        BigInteger x = this.s < 0 ? this.negate() : this.clones();
        BigInteger y = a.s < 0 ? a.negate() : a.clones();
        if (x.compareTo(y) < 0) {
            BigInteger t = x;
            x = y;
            y = t;
        }
        int i = x.getLowestSetBit();
        int g = y.getLowestSetBit();
        if (g < 0) {
            return x;
        }
        if (i < g) {
            g = i;
        }
        if (g > 0) {
            x.rShiftTo(g, x);
            y.rShiftTo(g, y);
        }
        while (x.signum() > 0) {
            i = x.getLowestSetBit();
            if (i > 0) {
                x.rShiftTo(i, x);
            }
            i = y.getLowestSetBit();
            if (i > 0) {
                y.rShiftTo(i, y);
            }
            if (x.compareTo(y) >= 0) {
                x.subTo(y, x);
                x.rShiftTo(Crypto.CRYPTO_NUMBER_1, x);
            } else {
                y.subTo(x, y);
                y.rShiftTo(Crypto.CRYPTO_NUMBER_1, y);
            }
        }
        if (g > 0) {
            y.lShiftTo(g, y);
        }
        return y;
    }

    // (protected) this % n, n < 2^26
    public int modInt(int n) {
        if (n <= 0) {
            return 0;
        }
        int d = Crypto.bIDV % n;
        int r = this.s < 0 ? n - 1 : 0;
        if (this.t > 0) {
            if (d == 0) {
                r = this.array.get(0) % n;
            } else {
                int i = this.t - 1;
                while (i >= 0) {
                    r = (d * r + this.array.get(i)) % n;
                    i -= 1;
                }
            }
        }
        return r;
    }

    // (public) 1/this % m (HAC 14.61)
    public BigInteger modInverse(BigInteger m) {
        boolean ac = m.isEven();
        if ((this.isEven() && ac) || m.signum() == 0) {
            return BigInteger.zero;
        }
        BigInteger u = m.clones();
        BigInteger v = this.clones();
        BigInteger a = BigInteger.nbv(1);
        BigInteger b = BigInteger.nbv(0);
        BigInteger c = BigInteger.nbv(0);
        BigInteger d = BigInteger.nbv(1);
        while (u.signum() != 0) {
            while (u.isEven()) {
                u.rShiftTo(1, u);
                if (ac) {
                    if (!a.isEven() || !b.isEven()) {
                        a.addTo(this, a);
                        b.subTo(m, b);
                    }
                    a.rShiftTo(1, a);
                } else if (!b.isEven()) {
                    b.subTo(m, b);
                }
                b.rShiftTo(1, b);
            }
            while (v.isEven()) {
                v.rShiftTo(1, v);
                if (ac) {
                    if (!c.isEven() || !d.isEven()) {
                        c.addTo(this, c);
                        d.subTo(m, d);
                    }
                    c.rShiftTo(1, c);
                } else if (!d.isEven()) {
                    d.subTo(m, d);
                }
                d.rShiftTo(1, d);
            }
            if (u.compareTo(v) >= 0) {
                u.subTo(v, u);
                if (ac) {
                    a.subTo(c, a);
                }
                b.subTo(d, b);
            } else {
                v.subTo(u, v);
                if (ac) {
                    c.subTo(a, c);
                }
                d.subTo(b, d);
            }
        }
        if (v.compareTo(BigInteger.one) != 0) {
            return BigInteger.zero;
        }
        if (d.compareTo(m) >= 0) {
            return d.subtract(m);
        }
        if (d.signum() < 0) {
            d.addTo(m, d);
        } else {
            return d;
        }
        if (d.signum() < 0) {
            return d.add(m);
        } else {
            return d;
        }
    }

    // (public) test primality with certainty >= 1-.5^t
    public boolean isProbablePrime(int t) {
        BigInteger x = this.abs();
        if (x.t == 1 && x.array.get(0) <= Crypto.lowprimes[Crypto.lowprimes.length - 1]) {
            for (int i = 0; i < Crypto.lowprimes.length; ++i) {
                if (x.array.get(0) == Crypto.lowprimes[i]) {
                    return true;
                }
            }
            return false;
        }
        if (x.isEven()) {
            return false;
        }
        int i = 1;
        while (i < Crypto.lowprimes.length) {
            int m = Crypto.lowprimes[i];
            int j = i + 1;
            while (j < Crypto.lowprimes.length && m < Crypto.lplim) {
                m *= Crypto.lowprimes[j];
                j += 1;
            }
            m = x.modInt(m);
            while (i < j) {
                if (m % Crypto.lowprimes[i] == 0) {
                    return false;
                }
                i += 1;
            }
        }
        return x.millerRabin(t);
    }

    // (protected) true if probably prime (HAC 4.24, Miller-Rabin)
    public boolean millerRabin(int t) {
        int tempT = t;
        BigInteger n1 = this.subtract(BigInteger.one);
        int k = n1.getLowestSetBit();
        if (k <= 0) {
            return false;
        }
        BigInteger r = n1.shiftRight(k);
        tempT = (tempT + 1) >> 1;
        if (tempT > Crypto.lowprimes.length) {
            tempT = Crypto.lowprimes.length;
        }
        BigInteger a = nbi();
        for (int i = 0; i < tempT; ++i) {
            a.fromInt(Crypto.lowprimes[i]);
            BigInteger y = a.modPow(r, this);
            if (y.compareTo(BigInteger.one) != 0 && y.compareTo(n1) != 0) {
                int j = 1;
                while (j < k && y.compareTo(n1) != 0) {
                    j += 1;
                    y = y.modPowInt(Crypto.CRYPTO_NUMBER_2, this);
                    if (y.compareTo(BigInteger.one) == 0) {
                        return false;
                    }
                }
                if (y.compareTo(n1) != 0) {
                    return false;
                }
            }
        }
        return true;
    }

    public int am(int i, int x, BigInteger w, int j, int c, int n) {
        return Crypto.aM.call(this.array, i, x, w, j, c, n);
    }
}

interface ConvertProtocol {
    BigInteger convert(BigInteger x);

    BigInteger revert(BigInteger x);

    void reduce(BigInteger x);

    void sqrTo(BigInteger x, BigInteger r);

    void mulTo(BigInteger x, BigInteger y, BigInteger r);
}

// Modular reduction using "classic" algorithm
class Classic implements ConvertProtocol {
    public BigInteger m;

    Classic(BigInteger m) {
        this.m = m;
    }

    @Override
    public BigInteger convert(BigInteger x) {
        if (x.s < 0 || x.compareTo(this.m) >= 0) {
            return x.mod(this.m);
        } else {
            return x;
        }
    }

    @Override
    public BigInteger revert(BigInteger x) {
        return x;
    }

    @Override
    public void reduce(BigInteger x) {
        x.divRemTo(this.m, null, x);
    }

    @Override
    public void sqrTo(BigInteger x, BigInteger r) {
        x.squareTo(r);
        this.reduce(r);
    }

    @Override
    public void mulTo(BigInteger x, BigInteger y, BigInteger r) {
        x.multiplyTo(y, r);
        this.reduce(r);
    }
}

// Montgomery reduction
class Montgomery implements ConvertProtocol {
    public BigInteger m;
    public int mp;
    public int mpl;
    public int mph;
    public int um;
    public int mt2;

    Montgomery(BigInteger m) {
        this.m = m;
        this.mp = m.invDigit();
        this.mpl = this.mp & Crypto.CRYPTO_NUMBER_0X7FFF;
        this.mph = this.mp >> Crypto.CRYPTO_NUMBER_15;
        this.um = (1 << (Crypto.bIDB - Crypto.CRYPTO_NUMBER_15)) - 1;
        this.mt2 = Crypto.CRYPTO_NUMBER_2 * m.t;
    }

    // xR mod m
    @Override
    public BigInteger convert(BigInteger x) {
        BigInteger r = BigInteger.nbi();
        x.abs().dlShiftTo(this.m.t, r);
        r.divRemTo(this.m, null, r);
        if (x.s < 0 && r.compareTo(BigInteger.zero) > 0) {
            this.m.subTo(r, r);
        }
        return r;
    }

    // x/R mod m
    @Override
    public BigInteger revert(BigInteger x) {
        BigInteger r = BigInteger.nbi();
        x.copyTo(r);
        this.reduce(r);
        return r;
    }

    // x = x/R mod m (HAC 14.32)
    @Override
    public void reduce(BigInteger x) {
        while (x.t <= this.mt2) {
            // pad x so am has enough room later
            x.array = Benchmark.insertValue(x.array, 0, x.t);
            x.t += 1;
        }
        for (int i = 0; i < this.m.t; ++i) {
            // faster way of calculating u0 = x[i]*mp mod DV
            int j = x.array.get(i) & Crypto.CRYPTO_NUMBER_0X7FFF;
            int u0 = (j * this.mpl + (((j * this.mph + (x.array.get(i) >> Crypto.CRYPTO_NUMBER_15) * this.mpl) & this.um) << Crypto.CRYPTO_NUMBER_15)) & Crypto.bIDM;
            // use am to combine the multiply-shift-add into one call
            j = i + this.m.t;
            int value = x.array.get(j) + this.m.am(0, u0, x, i, 0, this.m.t);
            x.array = Benchmark.insertValue(x.array, value, j);
            // propagate carry
            while (x.array.get(j) >= Crypto.bIDV) {
                x.array = Benchmark.insertValue(x.array, x.array.get(j) - Crypto.bIDV, j);
                j += 1;
                x.array = Benchmark.insertValue(x.array, x.array.get(j) + 1, j);
            }
        }
        x.clamp();
        x.drShiftTo(this.m.t, x);
        if (x.compareTo(this.m) >= 0) {
            x.subTo(this.m, x);
        }
    }

    // r = "x^2/R mod m"; x !== r
    @Override
    public void sqrTo(BigInteger x, BigInteger r) {
        x.squareTo(r);
        this.reduce(r);
    }

    // r = "xy/R mod m"; x,y !== r
    @Override
    public void mulTo(BigInteger x, BigInteger y, BigInteger r) {
        x.multiplyTo(y, r);
        this.reduce(r);
    }
}

class NullExp implements ConvertProtocol {
    @Override
    public BigInteger convert(BigInteger x) {
        return x;
    }

    @Override
    public BigInteger revert(BigInteger x) {
        return x;
    }

    @Override
    public void reduce(BigInteger x) {
        //debugLog('Method not implemented.')
    }

    @Override
    public void sqrTo(BigInteger x, BigInteger r) {
        x.squareTo(r);
    }

    @Override
    public void mulTo(BigInteger x, BigInteger y, BigInteger r) {
        x.multiplyTo(y, r);
    }
}

// Barrett modular reduction
class Barrett implements ConvertProtocol {
    public BigInteger r2;
    public BigInteger q3;
    public BigInteger mu;
    public BigInteger m;

    Barrett(BigInteger m) {
        // setup Barrett
        this.r2 = BigInteger.nbi();
        this.q3 = BigInteger.nbi();
        BigInteger.one.dlShiftTo(Crypto.CRYPTO_NUMBER_2 * m.t, this.r2);
        this.mu = this.r2.divide(m);
        this.m = m;
    }

    @Override
    public BigInteger convert(BigInteger x) {
        if (x.s < 0 || x.t > Crypto.CRYPTO_NUMBER_2 * this.m.t) {
            return x.mod(this.m);
        } else if (x.compareTo(this.m) < 0) {
            return x;
        } else {
            BigInteger r = BigInteger.nbi();
            x.copyTo(r);
            this.reduce(r);
            return r;
        }
    }

    @Override
    public BigInteger revert(BigInteger x) {
        return x;
    }

    // x = x mod m (HAC 14.42)
    @Override
    public void reduce(BigInteger x) {
        x.drShiftTo(this.m.t - 1, this.r2);
        if (x.t > this.m.t + 1) {
            x.t = this.m.t + 1;
            x.clamp();
        }
        this.mu.multiplyUpperTo(this.r2, this.m.t + 1, this.q3);
        this.m.multiplyLowerTo(this.q3, this.m.t + 1, this.r2);
        while (x.compareTo(this.r2) < 0) {
            x.dAddOffset(1, this.m.t + 1);
        }
        x.subTo(this.r2, x);
        while (x.compareTo(this.m) >= 0) {
            x.subTo(this.m, x);
        }
    }

    // r = x^2 mod m; x !== r
    @Override
    public void sqrTo(BigInteger x, BigInteger r) {
        x.squareTo(r);
        this.reduce(r);
    }

    // r = x*y mod m; x,y !== r
    @Override
    public void mulTo(BigInteger x, BigInteger y, BigInteger r) {
        x.multiplyTo(y, r);
        this.reduce(r);
    }
}

class Arcfour {
    public int i = 0;
    public int j = 0;
    public ArrayList<Integer> s = new ArrayList<>();

    // Initialize arcfour context from key, an array of ints, each from [0..255]
    public void arc4Init(ArrayList<Integer> key) {
        int j = 0;
        int t = 0;
        for (int i = 0; i < Crypto.CRYPTO_NUMBER_256; ++i) {
            Benchmark.insertValue(this.s, i, i);
        }
        for (int i = 0; i < Crypto.CRYPTO_NUMBER_256; ++i) {
            j = (int) ((j + this.s.get(i) + key.get(i % key.size())) & Crypto.CRYPTO_NUMBER_255);
            t = this.s.get(i);
            this.s = Benchmark.insertValue(this.s, this.s.get(j), i);
            this.s = Benchmark.insertValue(this.s, t, j);
        }
        this.i = 0;
        this.j = 0;
    }

    public int next() {
        int t;
        this.i = (this.i + 1) & Crypto.CRYPTO_NUMBER_255;
        this.j = (this.j + this.s.get(this.i)) & Crypto.CRYPTO_NUMBER_255;
        t = this.s.get(this.i);
        this.s = Benchmark.insertValue(this.s, this.s.get(this.j), this.i);
        this.s = Benchmark.insertValue(this.s, t, this.j);
        return this.s.get((t + this.s.get(this.i)) & Crypto.CRYPTO_NUMBER_255);
    }
}

// Plug in your RNG constructor here
class RngPool {
    public static Arcfour prngNewstate() {
        return new Arcfour();
    }

    // Pool size must be a multiple of 4 and greater than 32.
    // An array of bytes the size of the pool will be passed to init()
    public static int rngPsize = Crypto.CRYPTO_NUMBER_256;

    // For best results, put code like
    // <body onClick='rngSeedTime();' onKeyPress='rngSeedTime();'>
    // in your main HTML document.

    public static Arcfour rngState;
    public static ArrayList<Integer> rngPool;
    public static int rngPptr = 0;

    // Mix in a 32-bit integer into the pool
    public static void rngSeedInt(long x) {
        rngPool.set(rngPptr, rngPool.get(rngPptr) ^ ((int) (x & Crypto.CRYPTO_NUMBER_255)));
        rngPptr += 1;
        rngPool.set(rngPptr, rngPool.get(rngPptr) ^ ((int) (x >> Crypto.CRYPTO_NUMBER_8) & Crypto.CRYPTO_NUMBER_255));
        rngPptr += 1;
        rngPool.set(rngPptr, rngPool.get(rngPptr) ^ ((int) (x >> Crypto.CRYPTO_NUMBER_16) & Crypto.CRYPTO_NUMBER_255));
        rngPptr += 1;
        rngPool.set(rngPptr, rngPool.get(rngPptr) ^ ((int) (x >> Crypto.CRYPTO_NUMBER_24) & Crypto.CRYPTO_NUMBER_255));
        rngPptr += 1;
        if (rngPptr >= rngPsize) {
            rngPptr -= rngPsize;
        }
    }

    // Mix in the current time (w/milliseconds) into the pool
    public static void rngSeedTime() {
        // Use pre-computed date to avoid making the benchmark
        // results dependent on the current date.
        rngSeedInt(Crypto.CRYPTO_NUMBER_1122926989487);
    }

    // Initialize the pool with junk if needed.
    public static void initRngPool() {
        if (rngPool == null) {
            rngPool = new ArrayList<>();
            rngPptr = 0;
            int t;
            while (rngPptr < rngPsize) {
                // extract some randomness from Math.random()
                t = (int) Math.floor(Crypto.CRYPTO_NUMBER_65536 * Math.random());
                rngPool = Benchmark.insertValue(rngPool, (t >>> Crypto.CRYPTO_NUMBER_8), rngPptr);
                rngPptr += 1;
                rngPool = Benchmark.insertValue(rngPool, t & Crypto.CRYPTO_NUMBER_255, rngPptr);
                rngPptr += 1;
            }
            rngPptr = 0;
            rngSeedTime();
        }
    }
}

class SecureRandom {
    public void nextBytes(ArrayList<Integer> ba) {
        for (int i = 0; i < ba.size(); ++i) {
            ba = Benchmark.insertValue(ba, this.rngGetByte(), i);
        }
    }

    public int rngGetByte() {
        if (RngPool.rngState == null) {
            RngPool.rngSeedTime();
            RngPool.rngState = RngPool.prngNewstate();
            RngPool.rngState.arc4Init(RngPool.rngPool);
            RngPool.rngPptr = 0;
            while (RngPool.rngPptr < RngPool.rngPool.size()) {
                RngPool.rngPool = Benchmark.insertValue(RngPool.rngPool, 0, RngPool.rngPptr);
                RngPool.rngPptr += 1;
            }
            RngPool.rngPptr = 0;
        }
        // TODO: allow reseeding after first request
        return RngPool.rngState.next();
    }
}

// "empty" RSA key constructor
class RsaKey {
    public BigInteger n;
    public BigInteger d;
    public BigInteger p;
    public BigInteger q;
    public int e;
    public BigInteger dmp1;
    public BigInteger dmq1;
    public BigInteger coeff;

    RsaKey() {
        this.n = null; //default
        this.e = Crypto.CRYPTO_NUMBER_0;
        this.d = null; //default
        this.p = null; //default
        this.q = null; //default
        this.dmp1 = null; //default
        this.dmq1 = null; //default
        this.coeff = null; //default
    }

    // convert a (hex) string to a bignum object
    public BigInteger parseBigInt(String str, int r) {
        return new BigInteger(str, r);
    }

    public String linebrk(String s, int n) {
        String ret = "";
        int i = 0;
        while (i + n < s.length()) {
            ret += s.substring(i, i + n) + '\n';
            i += n;
        }
        return ret + s.substring(i, s.length());
    }

    public String byte2Hex(int b) {
        if (b < Crypto.CRYPTO_NUMBER_0X10) {
            return "0" + Integer.toString(b, Crypto.CRYPTO_NUMBER_16);
        } else {
            return Integer.toString(b, Crypto.CRYPTO_NUMBER_16);
        }
    }

    // PKCS#1 (type 2, random) pad input string s to n bytes, and return a bigint
    public BigInteger pkcs1pad2(String s, int n) {
        if (n < s.length() + Crypto.CRYPTO_NUMBER_11) {
            //debugLog('Message too long for RSA');
            return null;
        }
        int tempN = n;
        ArrayList<Integer> ba = new ArrayList<>();
        int i = s.length() - 1;
        while (i >= 0 && tempN > 0) {
            tempN -= 1;
            ba = Benchmark.insertValue(ba, s.codePointAt(i), tempN);
            i -= 1;
        }
        tempN -= 1;
        ba = Benchmark.insertValue(ba, 0, tempN);
        SecureRandom rng = new SecureRandom();
        ArrayList<Integer> x = new ArrayList<>();
        while (tempN > Crypto.CRYPTO_NUMBER_2) {
            // random non-zero pad
            x = Benchmark.insertValue(x, 0, 0);
            while (x.get(0) == 0) {
                rng.nextBytes(x);
            }
            tempN -= 1;
            ba = Benchmark.insertValue(ba, x.get(0), tempN);
        }
        tempN -= 1;
        ba = Benchmark.insertValue(ba, Crypto.CRYPTO_NUMBER_2, tempN);
        tempN -= 1;
        ba = Benchmark.insertValue(ba, 0, tempN);
        return new BigInteger(ba);
    }

    // Set the public key fields N and e from hex strings
    public void setPublic(String n, String e) {
        if (n.length() > 0 && e.length() > 0) {
            this.n = this.parseBigInt(n, Crypto.CRYPTO_NUMBER_16);
            this.e = Integer.parseInt(e, Crypto.CRYPTO_NUMBER_16);
        } else {
            //debugLog("Invalid RSA public key");
        }
    }

    // Perform raw public operation on "x": return x^e (mod n)
    public BigInteger doPublic(BigInteger x) {
        return x.modPowInt(this.e, this.n);
    }

    // Return the PKCS#1 RSA encryption of "text" as an even-length hex string
    public String encrypt(String text) {
        BigInteger m = this.pkcs1pad2(text, (this.n.bitLength() + Crypto.CRYPTO_NUMBER_7) >> Crypto.CRYPTO_NUMBER_3);
        if (m == null) {
            return null;
        }
        BigInteger c = this.doPublic(m);
        if (c == null) {
            return null;
        }
        String h = c.toString(Crypto.CRYPTO_NUMBER_16);
        if ((h.length() & 1) == 0) {
            return h;
        } else {
            return '0' + h;
        }
    }

    // Undo PKCS#1 (type 2, random) padding and, if valid, return the plaintext
    public String pkcs1unpad2(BigInteger d, int n) {
        ArrayList<Integer> b = d.toByteArray();
        int i = 0;
        while (i < b.size() && b.get(i) == 0) {
            i += 1;
        }
        if (b.size() - i != n - 1 || b.get(i) != Crypto.CRYPTO_NUMBER_2) {
            return null;
        }
        i += 1;
        while (b.get(i) != 0) {
            i += 1;
            if (i >= b.size()) {
                return null;
            }
        }
        String ret = "";
        i += 1;
        while (i < b.size()) {
            ret += (char) b.get(i).intValue();
            i += 1;
        }
        return ret;
    }

    // Set the private key fields N, e, and d from hex strings
    public void setPrivate(String n, String e, String d) {
        if (n.length() > 0 && e.length() > 0) {
            this.n = this.parseBigInt(n, Crypto.CRYPTO_NUMBER_16);
            this.e = Integer.parseInt(e, Crypto.CRYPTO_NUMBER_16);
            this.d = this.parseBigInt(d, Crypto.CRYPTO_NUMBER_16);
        } else {
            //debugLog("Invalid RSA private key");
        }
    }

    // Set the private key fields N, e, d and CRT params from hex strings
    public void setPrivateEx(String n, String e, String d, String p, String q, String dp, String dq, String c) {
        if (n.length() > 0 && e.length() > 0) {
            this.n = this.parseBigInt(n, Crypto.CRYPTO_NUMBER_16);
            this.e = Integer.parseInt(e, Crypto.CRYPTO_NUMBER_16);
            this.d = this.parseBigInt(d, Crypto.CRYPTO_NUMBER_16);
            this.p = this.parseBigInt(p, Crypto.CRYPTO_NUMBER_16);
            this.q = this.parseBigInt(q, Crypto.CRYPTO_NUMBER_16);
            this.dmp1 = this.parseBigInt(dp, Crypto.CRYPTO_NUMBER_16);
            this.dmq1 = this.parseBigInt(dq, Crypto.CRYPTO_NUMBER_16);
            this.coeff = this.parseBigInt(c, Crypto.CRYPTO_NUMBER_16);
        } else {
            //debugLog("Invalid RSA private key");
        }
    }

    // Generate a new random private key B bits long, using public expt E
    public void generate(int b, String e) {
        SecureRandom rng = new SecureRandom();
        int qs = b >> 1;
        this.e = Integer.parseInt(e, Crypto.CRYPTO_NUMBER_16);
        BigInteger ee = new BigInteger(e, Crypto.CRYPTO_NUMBER_16);
        while (true) {
            while (true) {
                this.p = new BigInteger(b - qs, 1, rng);
                if (this.p.subtract(BigInteger.one).gcd(ee).compareTo(BigInteger.one) == 0 && this.p.isProbablePrime(Crypto.CRYPTO_NUMBER_10)) {
                    break;
                }
            }
            while (true) {
                this.q = new BigInteger(qs, 1, rng);
                if (this.q.subtract(BigInteger.one).gcd(ee).compareTo(BigInteger.one) == 0 && this.q.isProbablePrime(Crypto.CRYPTO_NUMBER_10)) {
                    break;
                }
            }
            if (this.p.compareTo(this.q) <= 0) {
                BigInteger t = this.p;
                this.p = this.q;
                this.q = t;
            }
            BigInteger p1 = this.p.subtract(BigInteger.one);
            BigInteger q1 = this.q.subtract(BigInteger.one);
            BigInteger phi = p1.multiply(q1);
            if (phi.gcd(ee).compareTo(BigInteger.one) == 0) {
                this.dmp1 = this.d.mod(p1);
                this.dmq1 = this.d.mod(q1);
                this.n = this.p.multiply(this.q);
                this.d = ee.modInverse(phi);
                this.coeff = this.q.modInverse(this.p);
                break;
            }
        }
    }

    // Perform raw private operation on "x": return x^d (mod n)
    public BigInteger doPrivate(BigInteger x) {
        if (this.p == null || this.q == null) {
            return x.modPow(this.d, this.n);
        }
        // TODO: re-calculate any missing CRT params
        BigInteger xp = x.mod(this.p).modPow(this.dmp1, this.p);
        BigInteger xq = x.mod(this.q).modPow(this.dmq1, this.q);
        while (xp.compareTo(xq) < 0) {
            xp = xp.add(this.p);
        }
        return xp
                .subtract(xq)
                .multiply(this.coeff)
                .mod(this.p)
                .multiply(this.q)
				.add(xq);
    }

    // Return the PKCS#1 RSA decryption of "ctext".
    // "ctext" is an even-length hex string and the output is a plain string.
    public String decrypt(String ctext) {
        BigInteger c = this.parseBigInt(ctext, Crypto.CRYPTO_NUMBER_16);
        BigInteger m = this.doPrivate(c);
        if (m == null) {
            return null;
        }
        return this.pkcs1unpad2(m, (this.n.bitLength() + Crypto.CRYPTO_NUMBER_7) >> Crypto.CRYPTO_NUMBER_3);
    }
}

class Crypt {
    public static String nValue = "a5261939975948bb7a58dffe5ff54e65f0498f9175f5a09288810b8975871e99af3b5dd94057b0fc07535f5f97444504fa35169d461d0d30cf0192e307727c065168c788771c561a9400fb49175e9e6aa4e23fe11af69e9412dd23b0cb6684c4c2429bce139e848ab26d0829073351f4acd36074eafd036a5eb83359d2a698d3";
    public static String eValue = "10001";
    public static String dValue = "8e9912f6d3645894e8d38cb58c0db81ff516cf4c7e5a14c7f1eddb1459d2cded4d8d293fc97aee6aefb861859c8b6a3d1dfe710463e1f9ddc72048c09751971c4a580aa51eb523357a3cc48d31cfad1d4a165066ed92d4748fb6571211da5cb14bc11b6e2df7c1a559e6d5ac1cd5c94703a22891464fba23d0d965086277a161";
    public static String pValue = "d090ce58a92c75233a6486cb0a9209bf3583b64f540c76f5294bb97d285eed33aec220bde14b2417951178ac152ceab6da7090905b478195498b352048f15e7d";
    public static String qValue = "cab575dc652bb66df15a0359609d51d1db184750c00c6698b90ef3465c99655103edbf0d54c56aec0ce3c4d22592338092a126a0cc49f65a4a30d222b411e58f";
    public static String dmp1Value = "1a24bca8e273df2f0e47c199bbf678604e7df7215480c77c8db39f49b000ce2cf7500038acfff5433b7d582a01f1826e6f4d42e1c57f5e1fef7b12aabc59fd25";
    public static String dmq1Value = "3d06982efbbe47339e1f6d36b1216b8a741d410b0c662f54f7118b27b9a4ec9d914337eb39841d8666f3034408cf94f5b62f11c402fc994fe15a05493150d9fd";
    public static String coeffValue = "3a3e731acd8960b7ff9eb81a7ff93bd1cfa74cbd56987db58b4594fb09c09084db1734c8143f98b602b981aaa9243ca28deb69b5b280ee8dcee0fd2625e53250";

    public static String text = "The quick brown fox jumped over the extremely lazy frog! " + "Now is the time for all good men to come to the party.";
    public static String encrypted;

    public static void encrypt() {
        RsaKey RSA = new RsaKey();
        RSA.setPublic(nValue, eValue);
        RSA.setPrivateEx(nValue, eValue, dValue, pValue, qValue, dmp1Value, dmq1Value, coeffValue);
        encrypted = RSA.encrypt(text);
//        Benchmark.debugLog("text = " + text);
//        Benchmark.debugLog("encrypted = " + encrypted);
    }

    public static void decrypt() {
        RsaKey RSA = new RsaKey();
        RSA.setPublic(nValue, eValue);
        RSA.setPrivateEx(nValue, eValue, dValue, pValue, qValue, dmp1Value, dmq1Value, coeffValue);
        String decrypted = RSA.decrypt(encrypted);
        if (!decrypted.equals(text)) {
            // Benchmark.debugLog("Crypto operation failed");
        }
//        Benchmark.debugLog("decrypted = " + decrypted);
    }
}

/*
 * @State
 * @Tags Jetstream2
 */
class Benchmark {
    /*
     * @Setup
     */
    public void cryptoSetup() {
        Crypto.initBIRC();
        RngPool.initRngPool();
        Crypto.setupEngine(Crypto.am3, Crypto.CRYPTO_NUMBER_28);
    }

    /*
     * @Benchmark
     */
    public void runIteration() {
        Crypt.encrypt();
        Crypt.decrypt();
    }

    public static void cryptoRunIteration() {
        Benchmark benchmark = new Benchmark();
        double setupStart = System.nanoTime() / 1_000_000.0;
        benchmark.cryptoSetup();
        double setupEnd = System.nanoTime() / 1_000_000.0;
        //debugLog("setupTime: " + String(setupEnd - setupStart) + "ms");
        ArrayList<Double> runTimes = new ArrayList<>();
        double runStart =System.nanoTime() / 1_000_000.0;
        for (int index = 0; index < Crypto.CRYPTO_RUNCOUNT_120; index++) {
            double start = System.nanoTime() / 1_000_000.0;
            benchmark.runIteration();
            double end = System.nanoTime() / 1_000_000.0;
            double runtime = end - start;
            runTimes.add(runtime);
        // debugLog("onceRunTime: " + String(runtime) + "ms");
        }
        double endTime = System.nanoTime() / 1_000_000.0;
        // debugLog("runTime: " + String(endTime - runStart) + "ms");
        System.out.println("crypto: ms = " + (endTime - setupStart));
    }

    public static void debugLog(String str) {
        boolean isLog = false;
        if (isLog) {
            System.out.println(str);
        }
    }

    public static ArrayList<BigInteger> insertBigIntegerValue(ArrayList<BigInteger> array, BigInteger value, int i) {
        ArrayList<BigInteger> arr = array;
        if (i < arr.size()) {
            arr.set(i, value);
        } else {
            int surplus = i - arr.size();
            ArrayList<BigInteger> surplusArr = new ArrayList<>(Collections.nCopies(surplus + 1, null));
            arr.addAll(surplusArr);
            arr.set(i, value);
        }
        return arr;
    }

    public static ArrayList<Integer> insertValue(ArrayList<Integer> array, Integer value, int i) {
        ArrayList<Integer> arr = array;
        if (i < arr.size()) {
            arr.set(i, value);
        } else {
            int surplus = i - arr.size();
            ArrayList<Integer> surplusArr = new ArrayList<>(Collections.nCopies(surplus + 1, null));
            arr.addAll(surplusArr);
            arr.set(i, value);
        }
        return arr;
    }

    public static void main(String[] args) {
        cryptoRunIteration();
    }
}

@FunctionalInterface
interface AmBlock {
    int call(ArrayList<Integer> array, int i, int x, BigInteger w, int j, int c, int n);
}

@FunctionalInterface
interface OpBlock {
    int call(int x, int y);
}





